The present invention relates to the field of flash memory systems. More particularly, the present invention relates to flash memory systems implementing logical block address (LBA) to physical block address (PBA) correlation within a flash memory array.
Flash memory technology is an electrically rewritable nonvolatile digital memory technology that does not require a power source to retain its memory contents. A typical flash memory cell stores charge on a floating gate to represent a first logic state in the binary state system, while the lack of stored charge represents a second logic state in the binary state system. Additionally, a typical flash memory implementation is capable of supporting a write operation, a read operation, and an erase operation.
As flash memory technology has evolved, opportunities in a variety of applications have become possible. In particular, flash memory implementations that emulate the mass storage function of conventional rotating magnetic media, e.g., a hard disk drive or a floppy disk drive, coupled to a host computer system or other host digital system have gained wide acceptance. Hard disk drives and floppy disk drives suffer several deficiencies unseen in flash memory implementations. First, hard disk drives and floppy disk drives have many moving parts, i.e. an electrical motor, a spindle shaft, a read/write head, and a magnetizable rotating disk. These components give rise to reliability problems and magnify the hard disk drive""s and floppy disk drive""s susceptibility to failure resulting from the vibration and shock of being dropped or bumped. Secondly, hard disk drives and floppy disk drives consume a significant amount of power, thus quickly draining a portable computer""s battery. Finally, accessing data stored in the hard disk drive or the floppy disk is a relatively slow process.
In contrast, a typical flash memory system possesses many advantages over the hard disk drive and the floppy disk drive. The typical flash memory system has no moving parts, accounting for the higher reliability of the typical flash memory system. In addition, the rugged design of the typical flash memory system withstands environmental conditions and physical mishandling that would otherwise be catastrophic to the hard disk drive or the floppy disk drive. Generally, a user can access data stored in the typical flash memory system fairly quickly. Most significantly, the power consumption of the typical flash memory system is considerably lower than the hard disk drive""s and the floppy disk drive""s power consumption.
Although the typical flash memory system is ideally suited for mass storage applications, several properties associatedwith flash memory technology prevent the typical flash memory system from exactly replicating a data storage procedure implemented by the hard disk drive and the floppy disk drive. Maintaining compatibility with the data storage procedure implemented by the hard disk drive and the floppy disk drive is essential to the market success of the typical flash memory system because existing operating systems and existing application software are configured to operate with the data storage procedure implemented by the hard disk drive and the floppy disk drive.
One unique property of flash memory technology lies in the tendency of the typical flash memory cell to wear-out. This wearing-out property makes the typical flash memory cell unusable after a finite number of erase-write cycles. The data storage procedure implemented by the typical flash memory system must deal effectively with this finite life span of the typical flash memory cell.
Another unique property of flash memory technology is the inability to program the typical flash memory cell, if the typical flash memory cell is currently storing a particular logic state, without first performing the erase operation to erase the particular logic state before performing the write operation. Old data stored in the typical flash memory cell must be erased before attempting to program/write new data into the typical flash memory cell. Further limiting the performance of the typical flash memory system is the reality that the erase operation is a very time consuming operation relative to either the write operation or the read operation. Not only does the erase operation entail erasing the typical flash memory cell but additionally can results in the overerasure of the typical flash memory cell.
The data storage procedure implemented by the typical flash memory system minimizes the degradation in system performance associated with simply replicating the data storage procedure implemented by the hard disk drive and the floppy disk drive. The typical flash memory system endeavors to avoid writing the new data, or current version of data, in the typical flash memory cell storing the old data, or old version of the data, whenever possible to avoid performing the erase operation, unlike the hard disk drive and the floppy disk drive where the new data, or the current version of the data, is routinely programmed/written in a memory cell storing the old data, or the old version of the data. By writing the new data in an empty flash memory cell and by designating the typical flash memory cell which stores the old data as requiring the erase operation at a future convenient time, the typical flash memory system avoids performing the erase operation now, thus enhancing system performance. Additionally, to prevent certain typical flash memory cells from wearing-out and becoming unusable sooner than other typical flash memory cells, the typical flash memory system incorporates a wear leveling feature to regulate the usagexe2x80x94the number of erase-write cyclesxe2x80x94of the typical flash memory cells such that all storage regions of the typical flash memory system wear-out at a fairly consistent rate. The hard disk drive and the floppy disk drive do not require this wear leveling feature because their storage mechanisms can undergo a practically unlimited number of program/write operations without impacting performance.
The typical flash memory system comprises at least one typical flash memory device. FIG. 1 illustrates the arrangement of the typical flash memory cells in the typical flash memory device. A flash memory array 100 comprising typical flash memory cells functions as a nonvolatile mass memory component of the typical flash memory device. The flash memory array 100 is divided into a plurality of data blocks 102, . . . , 106 for storing data. The data blocks 102, . . . , 106 are conventionally labeled from zero to Mxe2x88x921, where M is the total number of data blocks 102 . . . , 106. Each data block 102, . . . , 106 is uniquely assigned a virtual physical block address (VPBA), the VPBA representing the typical flash memory system""s method of identifying and addressing the data blocks 102, . . . , 106 inside the typical flash memory device. Usually, each data block 102, . . . , 106 is selectively programmable and erasable. Furthermore, each data block 102, . . . , 106 includes a plurality of sectors 112 , . . . , 136. Within each data block 102, . . . , 106, the sectors 112, . . . , 136 are conventionally labeled from zero to Nxe2x88x921, where N is the number of sectors within each data block 102, . . . , 106. Since the data blocks 102, . . . , 106 comprise typical flash memory cells, the data blocks 102, . . . , 106 are nonvolatile, i.e., the data stored in the data blocks 102, . . . , 106 is retained even when power is cut off.
FIG. 2 illustrates the features of the sector 200 found in each data block. Typically, the sector 200 includes a plurality of fields 202, . . . , 212. A DATA field 202 is utilized for storing user data. Although the size of the DATA field 202 is typically five hundred twelve bytes which corresponds with a storage sector length in a commercially available hard disk drive or floppy disk drive, the DATA field 202 can be configured to be practically any length of bytes. An extension field 204, typically sixteen bytes, is seen to comprise an ECC field 206 for storing Error Correcting Code information associated with the DATA field 202 and is typically a length of four bytes. A virtual logical block address (VLBA) associated with the data stored in the DATA field 202 is typically stored in a LOGICAL BLOCK ADDRESS field 208 of only one sector 200 in each block 102, . . . , 106. Rather than storing all the bits of the LBA associated with the data stored in the DATA field 202 of a particular sector 200, only the higher order bits defining the VLBA are stored in the LOGICAL BLOCK ADDRESS field 208. Data from each of the component LBA""s which comprise the VLBA are stored in component sectors 112, . . . , 136 of data blocks"" PBA""s which comprise a VPBA in a manner which maintains correlation between the PBA""s and the LBA""s. This process is performed in conjunction with the space manager 300 discussed in greater detail in conjunction with FIG. 3. An incoming LBA of User Data has an address of higher order bits defining the general VLBA, and lower order bits defining the specific LBA. By initially masking the lower order bits, the processor defines the VLBA according to the higher order bits. The VLBA is then correlated to a specific VPBA of a Data Block 102, . . . , 106 through the space manager 300. Once the VLBA has been correlated to a VPBA, component LBA""s within a VLBA are then stored in component PBA""s of the corresponding VPBA through a concatenation process. The lower order bits of an incoming LBA are concatenated onto the VPBA to form a PBA defining a particular sector 112, . . . , 136 within a Data Block 102, . . . , 106. The logical block of incoming data is stored in that sector. In the data retrieval process, a similar process occurs. A host requests retrieval of a specific LBA. Again, the lower order bits are masked, and the higher order bits define the more general VLBA. Again, the VLBA is correlated to a VPBA through the space manager 300. When the Data Block 102, . . . , 106 defined by the VPBA is located, the lower order bits of the requested LBA are concatenated on the VTBA to form a PBA defining the exact sector 112, . . . , 136 where the data had been stored. The data is retrieved and sent to the host, defined according to the LBA by which the host requested it.
Because the masking and concatenation process briefly described above insures that the lower order bits of the logical address are the same as the lower order bits of the physical address, there is no need to store a correlation of the lower order bits. Accordingly, only the higher order bits comprising the VLBA are actually stored in the LOGICAL BLOCK ADDRESS field 208 of a physical sector 200. As a result, the LOGICAL BLOCK ADDRESS field 208 is typically a length of two bytes. However, this length can be increased or decreased depending on the amount of addressable storage capacity supported by the typical flash memory system. Because all of the sectors 112, . . . , 136 within a block 102, . . . , 106 of memory would store the same VLBA within their respective LOGICAL BLOCK ADDRESS, field 208, typically, the VLBA is stored in the LOGICAL BLOCK ADDRESS field 208 of only one sector 112, . . . , 136 per Data Block 102, . . . , 106.
A FLAG field 210 is employed for storing a plurality of flags pertaining to conditions of the data block of which the sector 200 is a part. The flags stored in the FLAG field 210 include a defective block flag, an old/new block flag for indicating if stored data is obsolete, and a used/free block flag. Also, the FLAG field 210 is typically a length of one byte. Finally, the sector 200 usually includes a plurality of SPARE bits 212 which are utilized when needed.
As described above, the typical flash memory system performs a data storage algorithm purposely designed to overcome the limitations of flash memory technology while retaining compatibility with existing operating systems and existing application software. One technique for implementing the data storage algorithm involves employing a space manager component to maintain a correlation between a virtual logical block addresses (VLBA) and a virtual physical block addresses (VPBA) of data stored in the typical flash memory system.
Because data cannot be re-programmed into a Flash Memory System without first engaging an erase process, an update of even a single LBA within a VLBA requires that the entire VLBA be re-written in a new Data Block 102, . . . , 106. As a result, a distinctive characteristic of the data storage algorithm implemented by the typical flash memory system lies in the continuously changing relation between the LBA and the PBA. Unlike the conventional rotating magnetic media where the LBA to PBA correlation is static because updated versions of the data are programmed over old versions of the data, the typical flash memory system must change the correlation between the LBA and the PBA because the updated versions of the data are programmed into empty memory locationsxe2x80x94inevitably having PBAs that are different from the PBA originally assigned to the LBAxe2x80x94rather than being programmed over the old versions of the data in memory locations having the PBA originally assigned to the LBA. As noted, the space manager 300 plays a critical role in coordinating LBA-to-PBA correlation in the typical flash memory system.
A host digital system, to which the typical flash memory system is coupled and to which the typical flash memory system provides nonvolatile mass storage, maintains organization of the data sent to the typical flash memory system by generating the LBA and associating the LBA with the data. The LBA is a logical address where the host digital system believes the data is stored in the typical flash memory system. Once the typical flash memory system receives the data and the LBA, the typical flash memory system transforms the LBA into the PBA, where the PBA is a physical address of the data block and a specific sector wherein the data is actually stored. As described above, each data block includes a plurality of sectors. Since the VPBA only refers to the data block rather than the actual sector storing the data within the data block, further reference must be made to the LBA to determine which sector within the data block stores the data. As noted, this involves the concatenation of a plurality of lower order bits of an LBA onto the lower end of the VPBA, thereby defining a PBA or physical address of the sector storing the data associated with the LBA. Each LBA within a VLBA is transformed into the physical address (the PBA) of one of the sectors. Hence, the typical flash memory system supports and recognizes a quantity of LBAs equal to the total number of sectors in the typical flash memory system. The bit length of the LBAs and the PBAs is directly related to the addressable storage capacity supported by the host digital system and the typical flash memory system.
Maintaining the correlation between LBAs and PBAs of the data stored in the typical flash memory system is critical to the proper operation of the typical flash memory system since the host digital system is generally not configured to track continually changing PBAs of the data stored in the typical flash memory system. The typical flash memory system transforms the LBA into the PBA upon initially receiving the data. Moreover, the typical flash memory system assigns an updated LBA to an entirely new PBA defining a sector 112, . . . , 136 which is part of an entirely new Data Block 102, . . . , 106 since it cannot program new data into an old PBA without first implementing an erase procedure. The procedure of storing updated data in a new physical location avoids the need to perform an erase-before-write cycle with each data update. As noted, the erase-before-write cycle degrades system performance. Reducing the number of the erase-before-write cycles improves system performance. As described above, if the typical flash memory cells are storing data, they can be reprogrammed only after the flash memory cells have been erased.
Refer to FIG. 3 for an illustration of the space manager 300 identified above. Typically, the space manager 300 is implemented as a volatile RAM array, the volatile RAM array including a plurality of volatile addressable memory locations 350, . . . , 358. Each volatile addressable memory location 350, . . . , 358 corresponds to one of the data blocks 102, . . . , 106 (FIG. 1) in the typical flash memory system and stores information about the corresponding data block 102, . . . , 106 (FIG. 1). FIG. 1. illustrated the data blocks 102, . . . , 106 conventionally labeled from zero to Mxe2x88x921. Similarly, the volatile addressable memory locations 350, . . . , 358 are conventionally labeled from zero to Mxe2x88x921 to reflect a label of the corresponding data block 102, . . . , 106 (FIG. 1). Additionally, each volatile addressable memory location 350, . . . , 358 is addressable by at least one of the VLBAs 360, . . . , 368 received from the host digital system and by one of the VPBAs 312, . . . , 320 of the typical flash memory system. Each volatile addressable memory location 350, . . . , 358 includes a plurality of fields 310, . . . , 340. Typically, the space manager 300 comprises static random access memory (SRAM) cells. However, other memory cells can be substituted for the SRAM cells.
Generally, the space manager 300 serves two purposes. First, the correlation between the virtual logical block address (VLBA) and the virtual physical block address (VPBA) of the data stored in the typical flash memory system is tracked in the space manager 300, giving the typical flash memory system rapid access to this crucial correlation information. A VPBA field 310 stores the VPBA assigned to the VLBA associated with the data received from the host digital system, where the VPBA is the address of the data block 102, . . . , 106 (FIG. 1) used to store data associated with a VLBA. The length of the VPBA field 310 is directly related to the addressable storage capacity supported by the typical flash memory system. Typically, the VPBA field 310 is a length of two bytes. Secondly, the typical flash memory system employs the space manager 300 to keep track of the flags associated with the data blocks 102, . . . , 106 (FIG. 1). Since each volatile addressable memory location 350, . . . , 358 corresponds to one of the data blocks 102, . . . , 106 (FIG. 1), the flags associated with the corresponding data block 102, . . . , 106 (FIG. 1) are maintained in flag fields 320, . . . , 340 within the volatile addressable memory location 350, . . . , 358. As described above, these flags include the defective block flag 320, the old/new or obsolete block flag 330, and the used/free block flag 340. Setting the defective block flag 320 of the data block 102, . . . , 106 (FIG. 1) causes the flash memory system to avoid storing the data in any of the sectors in the data block 102, . . . , 106 (FIG. 1) since the entire data block 102, . . . , 106 (FIG. 1) is deemed defective. Setting the used/free block flag 340 of the data block 102, . . . , 106 (FIG. 1) indicates the data block 102, . . . , 106 (FIG. 1) is currently storing data. An untransformed LBA would not be assigned a PBA of a sector within a data block 102, . . . , 106 (FIG. 1) currently storing data. Setting the old/new block flag 330 of the data block 102, . . . , 106 (FIG. 1) indicates the data block 102, . . . , 106 (FIG. 1) is storing an old version of the data, thus the data block 102, . . . , 106 (FIG. 1) must be erased before the data block 102, . . . , 106 (FIG. 1) can again be utilized for storing additional data.
In practice, when data defined by an LBA is received for the first time, the typical flash memory system utilizes the space manager 300 to search for the data block with an unset defective block flag 320 and an unset used/free block flag 340 for storing the data. The data is stored in the data block with the unset defective block flag 320 and the unset used/free block flag 340. In addition the VPBA of the data block with the unset defective block flag 320 and the unset used/free block flag 340 is stored in the VPBA field 310 of the volatile addressable memory location 350, . . . , 358 addressable by the VLBA 360, . . . , 368. The typical flash memory system also sets the used/free block flag 340 of the volatile addressable memory location 350, . . . , 358 addressable by the VPBA 312, . . . , 320 of the data block storing the data.
When the LBA and updated versions of the data are received such that the typical flash memory system must change a current PBA assigned to the LBA, the typical flash memory system proceeds as described above, thus avoiding the erase-before-write cycle. In addition, the typical flash memory system sets the old/new block flag 330 of the volatile addressable memory location 350, . . . , 358 addressable by the current VPBA 312, . . . , 320 to prevent the typical flash memory system from accessing unneeded versions of the data stored in the current PBA.
Also, the typical flash memory system employs the space manager 300 in performing the read operation. After the host digital system provides the LBA associated with requested data, the typical flash memory system locates the PBA assigned to the LBA by reading the contents of the VPBA field 310 of the volatile addressable memory location 350, . . . , 358 addressable by the LBA 360, . . . , 368. The typical flash memory system reads out the requested data from the data block whose PBA is assigned to the provided LBA.
Additionally, the space manager 300 assists the typical flash memory system in executing the erase operation. The typical flash memory system can perform the erase operation in the background, i.e., while another operation is being performed, or when necessary. Before initiating the erase operation, the typical flash memory system uses the space manager 300 to search for the data blocks having a set old/new block flag 330 and an unset defective block flag 320xe2x80x94these data blocks need to be erased. This search is conducted by examining the flag fields 320 and 330 (defective block and old/new or obsolete block) of the volatile addressable memory locations 350, . . . , 358. The typical flash memory system erases the data blocks having the set old/new block flag 330 and the unset defective block flag 320.
Due to the volatile nature of the space manager 300xe2x80x94loss of power causes the volatile RAM array to lose its memory contentsxe2x80x94, the information stored in the flag fields 320, . . . , 340 of each volatile addressable memory location 350, . . . , 358 is also stored in the FLAG field 210 (FIG. 2) of the corresponding data block. As noted, each VLBA having an assigned VPBA is stored in the LOGICAL BLOCK ADDRESS field 208 (FIG. 2) of the data block corresponding to the assigned VPBA. A distinct advantage of this feature rests in the non-volatile nature of the flash memory. Since the data blocks are nonvolatile, loss of power has no effect on the memory contents of the data blocks. This provides a non-volatile correlation between logical and physical addresses in the event of power loss.
During a power-up and during a system reset, the typical flash memory system restores the memory contents of the space manager 300. The FLAG field 210 (FIG. 2) of each data block is used to update the flag fields 320, . . . , 340 of the corresponding volatile addressable memory location 350, . . . , 358. Because a certain logical address is stored in the LOGICAL BLOCK ADDRESS field 208 (FIG. 2) of a sector of a particular data block 102, . . . , 106, during power-up or system reset, the controller is able to load the VPBA of the particular data block 102, . . . , 106 into an appropriate volatile addressable memory location 350, . . . , 358 corresponding to the appropriate VLBA 360, . . . , 368.
To control the operations of the typical flash memory system, the typical flash memory system further comprises a controller coupled to the typical flash memory device. Since the space manager 300 is an integral part of the operations performed by the typical flash memory system, the space manager 300 is typically designed within the controller. This increases system performance. Usually, the controller is formed on an integrated circuit separate from that on which the typical flash memory device is formed since the silicon area necessary for a large addressable storage capacity would generally make economically unfeasible formation of both the controller and the typical flash memory device on an identical integrated circuit. Additionally, formation of the controller on the separate integrated circuit allows the implementation of the controller in a manufacturing technology more suited for the performance demands placed on the controller by the typical flash memory system.
Although the space manager 300 enables the typical flash memory system to achieve superior performance, this superior performance, is attained at a significant cost in silicon area on the integrated circuit on which the controller is formed. Assume, for exemplary purposes only, a 64 MegaBit configuration for the typical flash memory system will enhance understanding of the problems associated with the space manager 300 of the prior art. The 64 MegaBit flash memory system comprises one 64 MegaBit flash memory device having 1024 data blocks, each data block including 16 sectors. This flash memory system supports 16,384 LBAs. The space manager 300 of the 64 MegaBit flash memory system will have 1024 volatile addressable memory locations 350, . . . , 358. The column containing the VPBA field 310 (which is two bytes in length) will occupy:
of volatile RAM memory space within the space manager 300. Although a length of 10 bits for the VPBA field 310 would be sufficient to store unique physical block addresses for the 1024 data blocks, manipulating PBAs which are identified in byte lengths (8 bits or multiples of 8 bits) optimizes operation of the typical flash memory system. Additionally, the 16 bit length of the VPBA field 310 accommodates expansion of the addressable storage capacity supported by the controller.
Unfortunately, the size of the space manager 300 within the controller increases significantly as the typical flash memory system is configured to support a larger amount of addressable storage capacity, as demonstrated by the calculations below.
Focusing on the 64 MegaByte flash memory system in TABLE 1, this flash memory system comprises eight 64 MegaBit flash memory devices. Similarly, the 128 MegaByte, 256 MegaByte, 512 MegaByte, and 1 GigaByte flash memory systems comprise a plurality of flash memory devices configured to store an appropriate amount of data. For the 1 GigaByte flash memory system, the length of the VPBA field 310 (FIG. 3) increased to 24 bits because 17 bits are required in order to store unique physical block addresses for the 131,072 data blocks and because a length of 3 bytes (24 bits) is the next available byte size. As is evident from TABLE 1, it is unpractical to implement space managers 300 (FIG. 3) of equivalent memory size in both large memory capacity and small memory capacity flash memory systems. Such implementation would increase the cost of the typical flash memory system and waste valuable silicon area on the integrated circuit on which the controller is formed. Hence, controllers having space managers 300 (FIG. 3) of vastly different memory sizes are required in order for the typical flash memory system to economically support increasing amounts of addressable storage capacity. In essence, the utility of the controller is limited by the size of the space manager 300 (FIG. 3).
What is needed is a new flash memory system implementing a new technique of keeping track of logical block address to physical block address correlation in order to reduce the logic circuit area devoted for the space manager in the controller and to expand the utility of the controller across a wide range of flash memory sizes.
The present invention is a flash memory system designed to reduce inefficiencies associated with keeping track of logical block address (LBA) to physical block address (PBA) correlation as practiced in the prior artxe2x80x94each logical block address generated by a host digital system and associated with data when the data is sent to be stored in the flash memory system by the host digital system. The flash memory system preferably comprises at least one flash memory device having a flash memory array, the flash memory array including a plurality of blocks for storing data and for storing a LBA-to-VPBA correlation, each block having a plurality of sectors, and a controller coupled to each flash memory device, the controller including a new space manager. By removing from the space manager of the prior art the task of tracking correlation between the LBA and the PBA of the data stored in the typical flash memory system of the prior art, considerable savings in manufacturing costs and logic circuit area on an integrated circuit are achieved and design flexibility attained. The new space manager of the present invention continues to keep track of the flags associated with the blocks in the flash memory system of the present invention. However, sufficient blocks are specifically reserved for keeping track of the LBA-to-VPBA correlation of the data stored in the flash memory system of the present invention and are referred to as correlation blocks. Each correlation block is configured to store the physical block addresses corresponding to a predetermined range of logical block addresses. Thus, each correlation block is associated with a predetermined range of logical block addresses although the physical block addresses are the addresses actually stored in each correlation block. Since the correlation blocks maintain their contents even when power is turned off, there is no need to maintain copies of the contents of the correlation blocks in other memory locations within the flash memory system.
To optimize performance of the flash memory system of the present invention, an erase-before-write cycle, i.e., performing an erase operation immediately before performing a write operation, is avoided whenever possible during the process of maintaining in the correlation blocks an accurate and updated correlation between the LBA and the PBA of the data stored in the flash memory system of the present invention. In particular, new correlation information, i.e., the new LBA-to-VPBA relation, is programmed into a free sector of an appropriate correlation block, i.e., a correlation block associated with the predetermined range of logical block addresses which includes the LBA or LBAs affected by the new correlation information, rather than erasing and then programming a previously programmed sector of the appropriate correlation block.
Each predetermined range of logical block addresses is associated with a current sector. Each current sector stores current correlation information, i.e., current LBA-to-VPBA relations, relating to the logical block addresses within the associated predetermined range of logical block addresses. In addition to programming the new correlation information into the free sector of the appropriate correlation block, the flash memory system of the present invention also simultaneously programs unchanged correlation information, i.e., unchanged LBA-to-VPBA relations, from the current sector into the free sector of the appropriate correlation block.
Programming correlation information, i.e., LBA-to-VPBA relations, into the correlation block is crucial to the proper operation of the flash memory system of the present invention. By coordinating a first programming operation, i.e., programming the data into an appropriate data block, and a second programming operation, i.e. programming the correlation information of the data into the appropriate correlation block, the flash memory system of the present invention optimizes system performance which would otherwise deteriorate because multiple programming operations are executed in the flash memory device, unlike the prior art where only the data has to be programmed into the typical flash memory device. In particular, programming the correlation information into the appropriate correlation block is kept as much as possible in the background, i.e., performed while another operation is being performed, or relegated to periods of system inactivity, i.e., performed when no other operation is being performed.
The flash memory system of the present invention preferably includes at least one alternate correlation block. Configured similarly to the correlation blocks, each alternate correlation block is associated with a primary correlation block and stores the physical block addresses corresponding to the predetermined range of logical block addresses associated with the primary correlation block. By having the alternate correlation block, the flash memory system of the present invention can store in the free sector of the alternate correlation block the new correlation information and the unchanged correlation information from the current sector when the free sector is not found in the primary correlation block. As a result, the flash memory system of the present invention avoids erasing the primary correlation block until a more convenient and, efficient time. Since the primary correlation block is erased before the alternate correlation block is completely filled, the primary correlation block is again available for storing the correlation information when the alternate correlation block is filled.
Additionally, the flash memory system of the present invention includes components for tracking each current sector and means for allocating a nondefective block to replace a defective correlation block. Having the components for tracking each current sector eliminates the need for performing read operations on the correlation block each time the flash memory system of the present invention accesses the correlation block in order to determine the free sector, thus improving system performance. Once a block is flagged as defective, the flash memory system of the present invention avoids accessing the defective block. Unlike the other blocks, correlation blocks are essential to the flash.memory system of the present invention. Hence, the nondefective block must be assigned to replace permanently the defective correlation block, a task accomplished by the means for allocating.
If the flash memory system of the present invention includes more than one flash memory device, system performance is enhanced by keeping track of the correlation between the LBAs and the PBAs of the data stored in a first flash memory device in the correlation block of a second flash memory device while keeping track of the correlation between the LBAs and the PBAs of the data stored in the second flash memory device in the correlation block of the first flash memory device. This technique maximizes system performance because the data and the correlation information can be programmed concurrently. Proceeding according to this technique enables the flash memory system of the present invention to program the correlation information relating to the data being stored in the first flash memory device into the correlation block of the second flash memory device while concurrently programming the data into the data block of the first flash memory device. Similarly, the flash memory system of the present invention can program the correlation information relating to the data being stored in the second flash memory device into the correlation block of the first flash memory device while concurrently programming the data into the data block of the second flash memory device.